package Week.w152;

import org.junit.Test;

import java.util.*;
import java.util.stream.Collectors;
public class Solution03 {
    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        if(queries==null||queries[0].length==0){
            return null;
        }
        List<Boolean> result=new ArrayList<>();
        for(int[] q:queries){
            String str=s.substring(q[0],q[1]+1);

            result.add(isPalindrome(str,q[2]));
        }
        return result;
    }




    public boolean isPalindrome(String s,int k) {
        if (s == null||s.length()<=1||k>s.length()) return true;
        char[] array=s.toCharArray();
        Arrays.sort(array);
        int singNum;
        if(s.length()%2==0){
            singNum=2*k;

        }else {
            singNum=2*k+1;
        }
        char[] chars=new char[26];
        for(int i=0;i<s.length();i++){
            chars[s.charAt(i)-'a']++;
        }

        for (char aChar : chars) {
            if (aChar % 2 == 1) {
                singNum--;
                if (singNum < 0) {
                    return false;
                }
            }
        }

        return true;
    }

    public List<Boolean> canMakePaliQueries2(String s, int[][] queries) {
        int n = s.length();
        int[][] cnt = new int[n][26];

        cnt[0][s.charAt(0) - 'a']++;
        for (int i = 1; i < n; ++i) {
            cnt[i][s.charAt(i) - 'a']++;
            for (int j = 0; j < 26; ++j) {
                cnt[i][j] += cnt[i - 1][j];
            }
        }

        List<Boolean> res = new ArrayList<>();
        for (int[] query: queries) {
            int l = query[0], r = query[1], k = query[2];
            if (k >= r - l + 1) {
                res.add(true);
                continue;
            }
            int odd = 0, even = 0;
            for (int i = 0; i < 26; ++i) {
                int p = l == 0 ?  cnt[r][i]: cnt[r][i] - cnt[l - 1][i];
                if (p > 0) {
                    if (p % 2 == 1) odd++;
                }
            }
            if ((odd / 2 <= k)||odd == 0 || (odd == 1 && k == 0 )) {
                res.add(true);
            }else {
                res.add(false);
            }
        }
        return res;
    }

    @Test
    public void test(){
        /*
        [[1,1,1],[2,3,0],[3,3,1],[0,3,2],[1,3,3],[2,3,1],[3,3,1],[0,3,0],[1,1,1],[2,3,0],[3,3,1],[0,3,1],[1,1,1]]
        * [true,false,true,true,true,true,true,false,true,false,true,true,true]
        *
        [0,3,1]
        true
        * */
        int[][] querys=new int[][]{{3,3,0},{1,2,0},{0,3,1},{0,3,2},{0,4,1}};
        canMakePaliQueries("abcda",querys);
    }
}
